package 力扣._6956_使循环数组所有元素相等的最少秒数;

import java.util.*;

public class Solution {
    public int minimumSeconds(List<Integer> nums) {
        //一轮中每个元素会变为它左右的元素之一，可循环
        //找到出现次数最多的节点
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> indexs = map.getOrDefault(nums.get(i), new ArrayList<>());
            indexs.add(i);
            map.put(nums.get(i), indexs);
        }

        int min_time = 9999999;
        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            //计算当前值的最短时间\
            int time;
            List<Integer> indexs = map.get(key);
            if (indexs.size() == 1) {
                time = nums.size() / 2;
                min_time = Math.min(time, min_time);
            } else {
                int longest_d = 0;
                int d;  //相邻下标间的距离
                //计算下标间的最长距离_由于按顺序读入，故下标一定有序
                for (int i = 0; i < indexs.size(); i++) {
                    int i1 = indexs.get(i);
                    int i2 = indexs.get((i + 1) % indexs.size());
                    if (i1 < i2) {
//                        d = Math.max((i2 - i1 - 1), nums.size() - i2 + i1 - 1);
                        d = i2 - i1 - 1;
                    } else {   //最后一个要特殊处理
                        d = nums.size() - i1 + i2 - 1;
                    }
                    longest_d = Math.max(longest_d, d);
                }
                time = (longest_d + 1) / 2;
                min_time = Math.min(time, min_time);
            }

        }
        return min_time;
    }

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(4);
        nums.add(18);
        int i = new Solution().minimumSeconds(nums);
        System.out.println(i);
    }
}
